# 力扣743. 网络延迟时间（来源：力扣）
# 有 n 个网络节点，标记为 1 到 n。给你一个列表 times，表示信号经过有向边的传递时间。
# times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点，w 是一个信号从源节点传递到目标节点的时间。
# 现在，从某个节点 k 发出一个信号，需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。
def solution(times, n, k):
    from collections import defaultdict
    import heapq

    # 构建图的邻接表
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))

    # 初始化距离数组，表示从 k 到每个节点的最短距离
    dist = {node: float('inf') for node in range(1, n + 1)}
    dist[k] = 0

    # 使用优先队列（堆）实现 Dijkstra 算法
    heap = [(0, k)]
    while heap:
        current_dist, u = heapq.heappop(heap)
        # 如果当前距离大于已知最短距离，跳过
        if current_dist > dist[u]:
            continue
        # 遍历邻居节点
        for v, w in graph[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))

    # 找到最大距离
    max_dist = max(dist.values())
    # 如果存在无法到达的节点，返回 -1
    return max_dist if max_dist < float('inf') else -1

# 时间复杂度：O(E log V)，其中 E 是边的数量，V 是节点数量
# 空间复杂度：O(V + E)，用于存储图和距离数组